/*!
 * \file GeneradorClique.cpp
 *
 * \date May 18, 2014
 * \author correa
 */
#include "GeneradorClique.h"

using namespace std;

GeneradorClique::GeneradorClique(const VertexSet * vertices, const ValueArray<double> * sol, bool creciente) : _vertices(vertices), _pesos(*sol),
		_Rsuelto(*(new VertexSet(_vertices->capacity()))), _orden(_vertices->lista()),
		_restante(*(new Lista(_vertices->capacity()))), _isDerived(false)
{
	if (creciente)
		_orden.crecientePesos(_pesos);
	else
		_orden.decrecientePesos(_pesos);
}

GeneradorClique::GeneradorClique(GeneradorClique * ec) : _vertices(ec->_vertices), _pesos(ec->_pesos),
		_Rsuelto(ec->_Rsuelto), _orden(ec->_orden),
		_restante(ec->_restante), _isDerived(true)
{
}

GeneradorClique::~GeneradorClique()
{
	if (!_isDerived) {
		delete &_Rsuelto;
		delete &_orden;
		delete &_restante;
	}
}

GeneradorClique * GeneradorClique::newInstance(Grafo * g, const SeparatorParameters * par) {
	return new GeneradorCliqueConGrafo(this, g, par);
}

GeneradorCliqueConGrafo::GeneradorCliqueConGrafo(GeneradorClique * ec, Grafo * g, const SeparatorParameters * par) : GeneradorClique(ec),
		_grafo(g), _param(par), _RR(new VertexSet*[_param->MAXCLIQUESZ]), _RRsuelto(new VertexSet(_grafo->getN())),
		_clique(_grafo->getN()), _cliqueWeight(0.0)
{
	for (int i = 0; i < _param->MAXCLIQUESZ; i++)
		_RR[i] = new VertexSet(_grafo->getN());

	_RR[0]->copyAll(*_vertices);
	_clique += -1;
}

GeneradorCliqueConGrafo::~GeneradorCliqueConGrafo()
{
	for (int i = 0; i < _param->MAXCLIQUESZ; i++)
		delete _RR[i];
	delete [] _RR;
	delete _RRsuelto;
}

bool GeneradorCliqueConGrafo::nextClique(ProjectableCliqueSet * c)
{
	int i, v;
	int npruevas = 0;

	while (_clique.cantidad() > 0 && ++npruevas <= 50)
	{
		for (i = _clique[_clique.cantidad()-1]+1; i < _orden.cantidad() && !_RR[_clique.cantidad()-1]->contains(_orden[i]); i++);

		if (i < _orden.cantidad())
		{
			v = _orden[i];
			_RR[_clique.cantidad()-1]->remove(v);
			--_clique;
			_clique += i;
			_cliqueWeight += _pesos[v];

			if (_clique.cantidad() == _param->MAXCLIQUESZ)
			{
				if (_cliqueWeight >= 0.65)
				{
					for (int j = 0; j < _clique.cantidad(); j++) {
						c->removeAll();
						c->add(_orden[_clique[j]], _pesos[_orden[_clique[j]]]);
					}

					_RR[_clique.cantidad()-1]->retainAll(_grafo->vecinos(v));
					//				cout << "(" << c->size() << "," << c->weight() << ")";
					//				c->print();

					for (int k = _clique.cantidad()-2; k >= 1; k--)
						_RR[_clique.cantidad()-1]->removeAll(*c);
					_cliqueWeight -= _clique[_clique.cantidad()-1];
					--_clique;
					return true;
				}
				_cliqueWeight -= _clique[_clique.cantidad()-1];
				--_clique;
			}
			else
			{
				_RR[_clique.cantidad()]->copyAll(*_RR[_clique.cantidad()-1]);
				_RR[_clique.cantidad()]->retainAll(_grafo->vecinos(v));

				if (_RR[_clique.cantidad()]->isEmpty()) //(isEmpty)
				{
					if (_cliqueWeight >= 0.65)
					{
						for (int j = 0; j < _clique.cantidad(); j++)
						{
							c->removeAll();
							c->add(_orden[_clique[j]], _pesos[_orden[_clique[j]]]);
						}

						//					cout << "(" << c->size() << "," << c->weight() << ")";
						//					c->print();
						return true;
					}
				}
				else
				{
					_cliqueWeight += _pesos[v];
					_clique += i;
				}
			}
		}
		else
		{
			_cliqueWeight -= _clique[_clique.cantidad()-1];
			--_clique;
		}
	}

	return false;
}

bool GeneradorCliqueConGrafo::nextCliqueParaMaximal(ProjectableCliqueSet * c)
{
	int i, v;

	while (_clique.cantidad() > 0)
	{
		for (i = _clique[_clique.cantidad()-1]+1; i < _orden.cantidad() && !_RR[_clique.cantidad()-1]->contains(_orden[i]); i++);

		if (i < _orden.cantidad())
		{
			v = _orden[i];
			_RR[_clique.cantidad()-1]->remove(v);
			--_clique;
			_clique += i;

			if (_clique.cantidad() == _param->MAXCLIQUESZ)
			{
				for (int j = 0; j < _clique.cantidad(); j++) {
					c->removeAll();
					c->add(_orden[_clique[j]], _pesos[_orden[_clique[j]]]);
				}

				_RR[_clique.cantidad()-1]->retainAll(_grafo->vecinos(v));
//				cout << "(" << c->size() << "," << c->weight() << ")";
//				c->print();

				for (int k = _clique.cantidad()-2; k >= 1; k--)
					_RR[_clique.cantidad()-1]->removeAll(*c);
				--_clique;
				return true;
			}

			if (_clique.cantidad() < _param->MAXCLIQUESZ)
			{
				_RR[_clique.cantidad()]->copyAll(*_RR[_clique.cantidad()-1]);
				_RR[_clique.cantidad()]->retainAll(_grafo->vecinos(v));

				if (_RR[_clique.cantidad()]->isEmpty()) //(isEmpty)
				{
					for (int j = 0; j < _clique.cantidad(); j++)
					{
						c->removeAll();
						c->add(_orden[_clique[j]], _pesos[_orden[_clique[j]]]);
					}

//					cout << "(" << c->size() << "," << c->weight() << ")";
//					c->print();
					return true;
				}
				_clique += i;
			}
		}
		else
		{
			--_clique;
		}
	}

	return false;
}

bool GeneradorCliqueConGrafo::nextCliqueMaximal(ProjectableCliqueSet * c)
{
	int npruebas = 0.0;
	while (++npruebas <= 50)
		if (nextCliqueParaMaximal(c))
		{
			if (c->size() == _param->MAXCLIQUESZ)
				cliqueSuelta(_RR[_clique.cantidad()], c);
			if (c->weight() >= 0.65)
				return true;
		}

	return false;
}

bool GeneradorCliqueConGrafo::hasNext()
{
	return _clique.cantidad() > 0;
}

bool GeneradorCliqueConGrafo::cliqueSuelta(const VertexSet * subgrafo, ProjectableCliqueSet * c)
{
	int v;
	int ret = c->size();
	_RRsuelto->copyAll(*subgrafo);

	int i;
	for (i = 0; i < _orden.cantidad(); i++) {
		v = _orden[i];
		if (_RRsuelto->contains(v))
		{
			c->add(v, _pesos[v]);
			ret--;
			_RRsuelto->retainAll(_grafo->vecinos(v));
		}
	}

//	cout << "(" << c.size() << "," << c.weight() << ")";

	return ret < 0;
}

bool GeneradorCliqueConGrafo::cliqueSueltaMaximal(const VertexSet * subgrafo, ProjectableCliqueSet * c)
{
	int v;
	int ret = c->size();
	_restante.clear();
	_Rsuelto.copyAll(*_vertices);
	_RRsuelto->copyAll(*subgrafo);

	int i;
	for (i = 0; i < _orden.cantidad(); i++) {
		v = _orden[i];
		if (_RRsuelto->contains(v))
		{
			c->add(v, _pesos[v]);
			ret--;
			_Rsuelto.retainAll(_grafo->vecinos(v));
			_RRsuelto->retainAll(_grafo->vecinos(v));
		}
		else if (!subgrafo->contains(v))
			_restante += v;
	}

	for (i = 0; i < _restante.cantidad(); i++) {
		v = _restante[i];
		if (_Rsuelto.contains(v))
		{
			c->add(v, _pesos[v]);
			ret--;
			_Rsuelto.retainAll(_grafo->vecinos(v));
		}
	}

	//	cout << "(" << c->size() << "," << c->weight() << ")" << endl;

	return ret < 0;
}

bool GeneradorCliqueConGrafo::cliqueNonArista(ProjectableCliqueSet * c) {
	int i = 0, j;
	double pij, cw;
	c->removeAll();
	VertexSet subgrafo(_grafo->getN());
	do
	{
		if (_pesos[_orden[i]] < 0.5)
			return false;
		j = i+1;
		do
		{
			cw = 0.0;
			pij = 0.0;
			while (j < _orden.cantidad() && _pesos[_orden[i]]+_pesos[_orden[j]] >= 1.0 && _grafo->isArista(_orden[j], _orden[i]))
				j++;

			if (j < _orden.cantidad())
			{
				pij = _pesos[_orden[i]] + _pesos[_orden[j]];
				if (pij >= 1.0)
				{
					subgrafo.copyAll(_grafo->vecinos(_orden[i]));
					subgrafo.addAll(_grafo->vecinos(_orden[j]));
					c->removeAll();
					cliqueSuelta(&subgrafo, c);
					if (c->size() > 1)
						cw = c->weight();
				}
				else
					j = _orden.cantidad();
			}
		} while (++j < _orden.cantidad() && pij + cw < 1.9);
	} while (++i < _orden.cantidad() && (j == _orden.cantidad() || pij + cw < 1.9));

	if (i == _orden.cantidad())
		return false;

	return true;
}
